This paper proposes a new replica placement algorithm that expands the exhaustive search limit with reasonable calculation time.\r\nIt combines a new type of parallel data-flow processor with an architecture tuned for fast calculation. The replica placement\r\nproblem is to find a replica-server set satisfying service constraints in a content delivery network (CDN). It is derived from the\r\nset cover problem which is known to be NP-hard. It is impractical to use exhaustive search to obtain optimal replica placement in\r\nlarge-scale networks, because calculation time increases with the number of combinations. To reduce calculation time, heuristic\r\nalgorithms have been proposed, but it is known that no heuristic algorithm is assured of finding the optimal solution. The proposed\r\nalgorithm suits parallel processing and pipeline execution and is implemented on DAPDNA-2, a dynamically reconfigurable\r\nprocessor. Experiments show that the proposed algorithm expands the exhaustive search limit by the factor of 18.8 compared\r\nto the conventional algorithm search limit running on a Neumann-type processor.
Loading....